<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    // 实现方式一  map实现方式  时间复杂度 O(2n) 空间复杂度O(n)
    const arr = [
      { id: 1, name: '部门1', pid: 0 },
      { id: 4, name: '部门4', pid: 3 },
      { id: 2, name: '部门2', pid: 1 },
      { id: 3, name: '部门3', pid: 1 },
      { id: 5, name: '部门5', pid: 4 },
    ]
    function arrayToTree1(items) {
      const map = new Map()
      const tree = []
      arr.forEach(item => {
        map.set(item.id, { ...item, children: [] })
      })
      arr.forEach(item => {
        const currentPid = map.get(item.pid)
        if (!currentPid) {
          tree.push(map.get(item.id))
        } else {
          currentPid.children.push(map.get(item.id))
        }
      })
      return tree
    }
    // [
    //   { id: 1, name: '部门1', pid: 0 },
    //   { id: 4, name: '部门4', pid: 3 },
    //   { id: 2, name: '部门2', pid: 1 },
    //   { id: 3, name: '部门3', pid: 1 },
    //   { id: 5, name: '部门5', pid: 4 },
    // ]

    function test(arr) {
      let tree = []
      let map = {}
      arr.forEach(item => {
        let id = item.id
        let pid = item.pid
        if(!map[id]) {
          // 没有就添加空children
          map[id] = { children: [] }
        }
        // 合并children
        let treeItem = (map[id] = { ...item, children: map[id].children })
        // 根节点id
        if(pid === 0) {
          tree.push(treeItem)
        }else {
          // pid不存在，map中就添加pid的chidlren信息
          if(!map[pid]) {
            map[pid] = { children: []}
          }
          map[pid].children.push(treeItem)
        }
      })
      return tree
    }
    // 方式二 通过map遍历添加数据的时候直接实现  时间复杂度O(n)
    function arrayToTree(items) {
      const result = [];   // 存放结果集
      const itemMap = {};  // 
      for (const item of items) {
        const id = item.id
        const pid = item.pid
        if (!itemMap[id]) {
          itemMap[id] = {
            children: []
          }
        }
        // 合并children
        itemMap[id] = { ...item, children: itemMap[id].children }
        const treeItem = itemMap[id]
        if (pid === 0) {
          result.push(treeItem)
        } else {
          // 没有pid，则直接添加到结果集
          if (!itemMap[pid]) {
            itemMap[pid] = {
              children: []
            }
          }
          itemMap[pid].children.push(treeItem)
        }
      }
      return result
    }

    console.log(arrayToTree(arr))
  </script>
</body>

</html>